package com.lw.leetcode.tree.a;

import com.lw.leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 653. 两数之和 IV - 输入 BST
 * 剑指 Offer II 056. 二叉搜索树中两个节点之和
 *
 * @Author liw
 * @Date 2021/5/30 15:11
 * @Version 1.0
 */
public class FindTarget {

    List<Integer> list = new ArrayList<>();

    public boolean findTarget(TreeNode root, int k) {
        find(root);
        List<Integer> l = list;
        int end = l.size() - 1;
        int st = 0;
        while (st < end) {
            int value = l.get(st) + l.get(end);
            if (value == k) {
                return true;
            } else if (value < k) {
                st++;
            } else {
                end--;
            }
        }
        return false;
    }

    public void find(TreeNode node) {
        if (node == null) {
            return;
        }
        find(node.left);
        list.add(node.val);
        find(node.right);
    }

}
